package leetcode.medium.q380;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

public class RandomizedSet {
    private Random random =new Random();
    private Map<Integer,Integer> indexMap =new HashMap<>();
    private List<Integer> vals =new ArrayList<>();
    public RandomizedSet() {

    }

    public boolean insert(int val) {
        if (indexMap.containsKey(val)) {
            return false;
        }
        vals.add(val);
        indexMap.put(val,vals.size()-1);
        return true;
    }

    public boolean remove(int val) {
        if (!indexMap.containsKey(val)){
            return false;
        }
        int i = indexMap.get(val);
        Integer last = vals.get(vals.size() - 1);
        /**
         * ArrayList 只有移除最后一个是O(1)
         * ，为什么不用LinkedList？
         * ----》remove动作简单，但是从中间移除会导致所有节点 index改变，还是只能中部node替换，末尾移除
         * 而LinkedList的set(index,val)，反而性能比ArrayList性能低
         */
        vals.set(i,last);
        indexMap.put(last,i);
        vals.remove(vals.size()-1);
        indexMap.remove(val);
        return true;
    }

    public int getRandom() {
        int nextInt = random.nextInt(vals.size());
        return vals.get(nextInt);
    }
}
